#include <iostream>
#include <vector>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<time.h>
#include "AVL.h"
#include "splay.h"
using namespace std;
#define N 600



template <typename T>
void  Random(std::vector<T> &_data)
{
    T middle;
    size_t tmp;
    unsigned seed;
    seed = time(0);
    srand(seed);
    for(size_t i = 0; i<_data.size();i++)
    {
        tmp = rand()%_data.size();
        middle = _data[i];
        _data[i] = _data[tmp];
        _data[tmp] = middle;
    }
    /*std::cout<<"打乱顺序后的向量次序为："<<std::endl;
    for(size_t i = 0; i<_data.size();i++) 
    {
        std::cout<<_data[i]<<"  ";
    }
    std::cout<<std::endl<<std::endl;
    */
}

template <typename T>
void Randomized_AVL_sort(std::vector<T> &_data)
{
    vector<T> ret;
    AvlTree<T> bst;
    for(size_t i = 0; i<_data.size();i++)       
    {
        bst.insert(_data[i]);           //数据插入
    }
    
    bst.InorderTravesal(ret);           //中序遍历到ret中
    if(_data.size() != ret.size()) 
    {
        std::cout<<"error size";        //防止出错
        return;
    }
    /*std::cout<<"中序遍历的输出结果是："<<std::endl;
    for(size_t i = 0; i<ret.size();i++) //向量拷贝
    {
        _data[i]=ret[i];
        std::cout<<_data[i]<<"  ";
    }
    std::cout<<std::endl<<std::endl;
*/
}

template <typename T>
void Randomized_SPLAY_sort(std::vector<T> &_data)
{
    vector<T> ret;
    SplayTree<T> bst;
    for(size_t i = 0; i<_data.size();i++)       
    {
        bst.insert(_data[i]);           //数据插入
    }

    bst.InorderTravesal(ret);           //中序遍历到ret中
    if(_data.size() != ret.size()) 
    {
        std::cout<<"error size";        //防止出错
        return;
    }
    /*std::cout<<"中序遍历的输出结果是："<<std::endl;
    for(size_t i = 0; i<ret.size();i++) //向量拷贝
    {
        _data[i]=ret[i];
        std::cout<<_data[i]<<"  ";
    }
    std::cout<<std::endl<<std::endl;
    */
}

    // Test program
int main( )
{
    vector<int> vec1(100);
    for(int i = 0; i<vec1.size();i++)
    {
        vec1[i] = i;
    }
    
    std::cout<<"原始向量为："<<std::endl;
    for(size_t i = 0; i<vec1.size();i++) {std::cout<<vec1[i]<<"  ";}
    std::cout<<std::endl<<std::endl;
    double time1 = 0;
    double time2 = 0;
    for(int i =1; i<=N ; i++)
    {
        Random(vec1);
        clock_t t1,t2;
        t1 = clock();
        Randomized_AVL_sort(vec1);
        t2 = clock();
        time1 += double(t2-t1);
    }

    for(int i =1; i<=N ; i++)
    {
        Random(vec1);
        clock_t t1,t2;
        t1 = clock();
        Randomized_SPLAY_sort(vec1);
        t2 = clock();
        time2 += double(t2-t1);
    }
    cout<<"AVL sort time: "<<time1<<"ms"<<endl;
    cout<<"Splay sort time: "<<time2<<"ms"<<endl;
    
    return 0;
}
  
    
    
/*
    // Test program
int main( )
{
    AvlTree<int> t;
    int NUMS = 2000000;
    const int GAP  =   37;
    int i;

    cout << "Checking... (no more output means success)" << endl;

    for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
        t.insert( i );
    t.remove( 0 );
    for( i = 1; i < NUMS; i += 2 )
        t.remove( i );

    if( NUMS < 40 )
        t.printTree( );
    if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
        cout << "FindMin or FindMax error!" << endl;

    for( i = 2; i < NUMS; i += 2 )
        if( !t.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS; i += 2 )
    {
        if( t.contains( i )  )
            cout << "Find error2!" << endl;
    }

    AvlTree<int> t2;
    t2 = t;

    for( i = 2; i < NUMS; i += 2 )
        if( !t2.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS; i += 2 )
    {
        if( t2.contains( i ) )
            cout << "Find error2!" << endl;
    }

    cout << "End of test..." << endl;
    return 0;
}
*/
